/**
 * 给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *链表中节点的数目在范围 [0, 5 * 104] 内
 * -10^5 <= Node.val <= 10^5
 *你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
 * https://leetcode.cn/problems/7WHec2/
 */
class SortList {
    public ListNode sortList(ListNode head) {
        int[] arr=new int[200000];
        ListNode cur=head;
        while(cur!=null){
            arr[.val+100000]++;
            cur=cur.next;
        }
        cur=head;
        for(int i=0;i<200000&&cur!=null;i++){
            while(arr[i]!=0){
                cur.val=i-100000;
                cur=cur.next;
                arr[i]--;
            }
        }
        return head;
    }
}